<?php
/**
 * @category Goatherd
 * @package Goatherd\Commons
 *
 * @author Copyright (c) 2012 Maik Penz <maik@phpkuh.de>
 * @version $Id: Gaddag.php 95 2012-04-27 01:18:10Z maik@phpkuh.de $
 *
 * This file is part of Goatherd library.
 *
 * Goatherd library is free software: you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Goatherd library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Goatherd library. If not, see <http://www.gnu.org/licenses/>.
 */
namespace Goatherd\Commons\Word;

/**
 * DAWG for {REV(x)#y | xy is word && x is not empty} with # being a seperator
 * not allowed in words (http://en.wikipedia.org/wiki/GADDAG).
 *
 * @package Goatherd\Commons
 * @subpackage Word
 */
class Gaddag
extends Dawg
{
    /**
     *
     * @var string
     */
    const DEFAULT_GADDAG_SEPARATOR = '#';

    /**
     *
     * @var string
     */
    protected $_gaddagSeparator = self::DEFAULT_GADDAG_SEPARATOR;

    /**
     *
     * @return string
     */
    public function getSeparator()
    {
        return $this->_gaddagSeparator;
    }

    /**
     *
     * @param string $word
     * @return array
     */
    public function getWordIndex($word)
    {
        $letters = $this->split($word);
        $words = array();

        $i = count($letters);
        if ($i > 1) {
            for ($pos = 1; $pos < $i; $pos++) {
                $x = array_slice($letters, 0, $pos);
                $x = implode(array_reverse($x));

                $y = array_slice($letters, $pos);
                $y = implode($y);

                $words[] = ($x . $this->_gaddagSeparator . $y);
            }
            $words[] = implode(array_reverse($letters));
        } else {
            $words = array($word);
        }

        return $words;
    }

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.Dawg::add()
     */
    public function add($word)
    {
        $words = $this->getWordIndex($word);

        foreach ($words as $word) {
            parent::add($word);
        }
    }

    /**
     * (non-PHPdoc)
     * @see Goatherd\Commons\Word.Trie::has()
     */
    public function has($word)
    {
        $letters = $this->split($word);
        $node = &$this->_trie;
        foreach ($letters as $letter) {
            if (!isset($node[$letter])) {
                if (isset($node[$this->_gaddagSeparator])
                     && isset($node[$this->_gaddagSeparator][$letter])) {
                    $node = &$node[$this->_gaddagSeparator];
                } else {
                    return false;
                }
            }
            $node = &$node[$letter];
        }

        return $node === true || isset($node[self::END_OF_WORD]);
    }
}